package Easy;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

// 993.二叉树的堂兄弟结点
public class Solution993 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        if (root.val == x || root.val == y)
            return false;
        // 如果深度相同，且不是同一个父亲，则返回true
        // 当深度为h的时候，应该弹出2的h次方个结点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> tempQueue = new LinkedList<TreeNode>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            // 弹出所有的元素，此时弹出的元素都在同一层
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                tempQueue.offer(poll);
            }
            // 分别将这些元素的孩子加入队列queue，如果两个孩子正好是x和y，返回false
            // 如果所有的孩子加完以后,只有一个x或者y，则返回false
            // 如果能找到不同父亲的两个孩子，则返回true
            while (!tempQueue.isEmpty()) {
                TreeNode poll = tempQueue.poll();
                if (poll.left != null && poll.right != null) {
                    if ((poll.left.val == x && poll.right.val == y) || (poll.left.val == y && poll.right.val == x))
                        return false;
                    queue.offer(poll.left);
                    if (poll.left.val == x || poll.left.val == y) count++;
                    queue.offer(poll.right);
                    if (poll.right.val == x || poll.right.val == y) count++;
                } else if (poll.left != null){
                    queue.offer(poll.left);
                    if (poll.left.val == x || poll.left.val == y) count++;
                }else if(poll.right != null){
                    queue.offer(poll.right);
                    if (poll.right.val == x || poll.right.val == y) count++;
                }
            }
            if(count == 1)return false;
            if(count == 2)return true;
        }
        return false;
    }
}
